package msb.class07;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * 给定很多线段，每个线段都有左右两个位置 [ start,  end ]，表示线段开始位置和结束位置，左右都是闭区间
 * 规定：
 * 线段开始和结束位置一定是整数
 * 线段重合区域的长度必须 >= 1
 * 返回线段最多重合区域中，包含了几条线段
 * <p>
 * <p>
 * 解法
 * 1. 起点排序
 * 2. 终点入小根堆，从堆顶小于当前起点则弹出，剩余堆长度为当前重合线段值
 */
public class Code03_CoverMax {

    public static int maxCover(int[][] input) {
        //将lines转换为int[][]数组
        Arrays.sort(input, Comparator.comparingInt(o -> o[0]));
        System.out.println(Arrays.deepToString(input));
        int max = 0;
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < input.length; i++) {
            while (heap.size() > 0 && input[i][0] >= heap.peek()) {
                heap.poll();
            }
            heap.add(input[i][1]);
            max = Math.max(heap.size(), max);
        }
        return max;
    }


    /**
     * 对数器
     *
     * @param args
     */
    public static void main(String[] args) {
        int[][] input = generateInput(10, 0, 100);
//        int[][] input = readInput("[[18, 37], [19, 21], [58, 99], [65, 87], [67, 95], [72, 85], [77, 89], [83, 83], [91, 99], [92, 98]]");
        int expectedOutput = getExpectedOutput(input);
        int actualOutput = Code03_CoverMax.maxCover(input);
        if (actualOutput != expectedOutput) {
            System.out.println("Test failed!");
            System.out.println("Input: " + Arrays.deepToString(input));
            System.out.println("Expected output: " + expectedOutput);
            System.out.println("Actual output: " + actualOutput);
        } else {
            System.out.println("Test passed!");
        }
    }

    private static int[][] generateInput(int n, int minValue, int maxValue) {
        int[][] input = new int[n][2];
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            int start = random.nextInt(maxValue - minValue + 1) + minValue;
            int end = random.nextInt(maxValue - start + 2) + start;
            input[i][0] = start;
            input[i][1] = end;
        }
        return input;
    }

    /**
     *
     * @param input
     * @return
     */
    public static int getExpectedOutput(int[][] input) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < input.length; i++) {
            min = Math.min(min, input[i][0]);
            max = Math.max(max, input[i][1]);
        }
        int cover = 0;
        for (double p = min + 0.5; p < max; p += 1) {
            int cur = 0;
            for (int i = 0; i < input.length; i++) {
                if (input[i][0] <= p && input[i][1] >= p) {
                    cur++;
                }
            }
            cover = Math.max(cover, cur);
        }
        return cover;
    }

    private static boolean overlap(int[] a, int[] b) {
        return Math.max(a[0], b[0]) <= Math.min(a[1], b[1]);
    }


    public static int[][] readInput(String inputStr) {
        String[] pairs = inputStr.split("], \\[");
        int[][] output = new int[pairs.length][2];
        for (int i = 0; i < pairs.length; i++) {
            String[] pair = pairs[i].replaceAll("\\[", "").replaceAll("]", "").split(", ");
            output[i][0] = Integer.parseInt(pair[0]);
            output[i][1] = Integer.parseInt(pair[1]);
        }
        return output;
    }

}
